package com.algorithm.base.greedy;

import org.springframework.stereotype.Service;

import java.util.Arrays;

/**
 * 134. 加油站
 *
 * @author Amadeus
 * @date 2023/11/23
 */
@Service
public class CanCompleteCircuit {

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int sum = 0;
        int totalSum = 0;
        int index = 0;
        for (int i = 0; i < gas.length; i++) {
            sum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            if (sum < 0) {
                index = (i + 1) % gas.length;
                sum = 0;
            }
        }
        if (totalSum < 0) {
            return -1;
        }
        return index;
    }

}
